package com.xyhuo.leetcode.january;

import java.util.HashMap;
import java.util.Map;

/**
 * 不同的二叉搜索树
 * https://leetcode.cn/problems/unique-binary-search-trees/
 *
 * @time 2024/1/5
 */
public class NumTrees {

//    public static void main(String[] args) {
//        NumTrees nt = new NumTrees();
//        nt.numTrees(3);
//    }

    public int numTrees(int n) {
        map.put(0, 1);
        map.put(1, 1);
        map.put(2, 2);
        return search(0, n - 1);
    }

    private Map<Integer, Integer> map = new HashMap<>();

    private int search(int left, int right) {
        if (map.containsKey(right - left + 1)) {
            return map.get(right - left + 1);
        }
        int ans = 0;
        for (int i = left; i <= right; i++) {
            int leftBet = i - left;
            int leftVal;
            if (map.containsKey(leftBet)) {
                leftVal = map.get(leftBet);
            } else {
                leftVal = search(left, i - 1);
            }

            int rightBet = right - i;
            int rightVal;
            if (map.containsKey(rightBet)) {
                rightVal = map.get(rightBet);
            } else {
                rightVal = search(i + 1, right);
            }
            ans += leftVal * rightVal;
        }
        map.put(right - left + 1, ans);
        return ans;
    }
}
